count_v2 = 0
count_v3 = 0

import sys

def get_greatest_common_divisor_v2(a, b):
    global count_v2
    count_v2 += 1
    print('v2============:' + str(count_v2))
    big = max(a, b)
    small = min(a, b)
    temp = big % small
    if temp == 0:
        return small
    return get_greatest_common_divisor_v2(temp, small)


def get_greatest_common_divisor_v3(a, b):
    global count_v3
    count_v3 += 1
    print('v3============:' + str(count_v3))
    if a == b:
        return a
    big = max(a, b)
    small = min(a, b)
    return get_greatest_common_divisor_v2(big - small, small)


def get_greatest_common_divisor_v4(a, b):
    if a == b:
        return a
    # 均为偶数
    if (a & 1) == 0 and (b & 1) == 0:
        return get_greatest_common_divisor_v4(a >> 1, b >> 1) << 1
    # a为偶数，b为奇数
    elif (a & 1) == 0 and (b & 1) != 0:
        return get_greatest_common_divisor_v4(a >> 1, b)
    # a为奇数，b为偶数
    elif (a & 1) != 0 and (b & 1) == 0:
        return get_greatest_common_divisor_v4(a, b >> 1)
    else:
        big = max(a, b)
        small = min(a, b)
        return get_greatest_common_divisor_v4(big - small, small)


if __name__ == '__main__':
    # print(get_greatest_common_divisor_v2(1002, 1003))
    # print(get_greatest_common_divisor_v3(1002, 1003))
    print(get_greatest_common_divisor_v4(1002, 1003))
